package org.example.SolutionNew003;

import java.util.*;

public class DoubleTree010 {
    public static void main(String[] args) {
        DoubleTree010 dt=new DoubleTree010();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.right.right = new TreeNode(3);
        root.left.right = new TreeNode(3);
        root.left.right.right = new TreeNode(3);
        System.out.println(dt.rightSideView(root).toString());

    }

    //层序遍历
    public List<Integer> rightSideView1(TreeNode root) {
        //层序遍历的每层最后一个
        List<Integer> res=new ArrayList<>();
        if(root==null) return res;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int size=queue.size();
            while(size!=0){
                TreeNode node=queue.poll();
                if(size==1){
                    res.add(node.val);
                }
                if(node.left!=null) queue.offer(node.left);
                if(node.right!=null) queue.offer(node.right);
                size--;
            }
        }
        return res;
    }

    //深度+栈（从左节点插到右节点，这样使用栈就会优先弹出右节点）
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        if(root==null) return res;

        int max_depth=-1;
        Map<Integer,Integer> map=new HashMap<>();   //存储碰到的层数以及其最右边的节点的值（栈的特性）
        Stack<TreeNode> nodeStack=new Stack<>();
        Stack<Integer> depthStack=new Stack<>();
        nodeStack.push(root);
        depthStack.push(0);

        while(!nodeStack.isEmpty()){
            TreeNode node=nodeStack.pop();
            int depth=depthStack.pop();

            if(node!=null){
                max_depth=Math.max(max_depth,depth);

                if(!map.containsKey(depth)){
                    map.put(depth,node.val);
                }

                nodeStack.push(node.left);
                nodeStack.push(node.right);
                depthStack.push(depth+1);
                depthStack.push(depth+1);
            }

        }

        for(int i=0;i<=max_depth;i++){
            res.add(map.get(i));
        }
        return res;
    }
}
